/*
 * Copyright 北京航空航天大学  @ 2015 版权所有
 */
package com.buaa.edu.leetcode.algorithm.array;

/**
 * <p>
 * 搜索元素并插入到适当的位置
 *  [1,3,5,6], 5 → 2 
 *  [1,3,5,6], 2 → 1 
 *  [1,3,5,6], 7 → 4 
 *  [1,3,5,6], 0 → 0
 * </p>
 * 
 * @author towan
 * @email tongwenzide@163.com
 * @time 2015年6月22日
 */
public class SearchInsertPosition {

    public int searchInsert(int[] nums, int target) {
        int low = 0;
        int high = nums.length-1;
        int mid = 0;
        while(low<=high){
            mid = (low+high)/2;
            if(nums[mid]==target){
                return mid;
            }else if(nums[mid]>target){
                high = mid-1;
            }else{
                low = mid +1;
            }
        }
        return low;
    }
}
